package com.github.hgkmail.hello.leetcode101.dp.sub;

import java.util.Arrays;

//严格递增子序列
//sub: subsequence(子序列 不用连续), substring(子串 需要连续), sub array(子数组 需要连续)
//一维数组dp，经典切入口：以第i位结尾（含有第i位）的子数组作为子问题。
//二维数组dp，经典切入口：以点P(i,j)结尾（含有点P(i,j)）的子图作为子问题。
public class LC300LongestIncreasingSubsequence {
    public int lengthOfLIS(int[] nums) {
        int len=nums.length;
        if (len<=0) {
            return 0;
        }
        int[] dp=new int[len];
        Arrays.fill(dp, 1); //数列最小长度是1，单个数
        for (int i = 0; i < len; i++) {
            for (int j = i-1; j >=0 ; j--) {
                if (nums[i]>nums[j]) {
                    dp[i]=Math.max(dp[i], dp[j]+1);
                }
            }
        }
        return Arrays.stream(dp).max().getAsInt();
    }

    public static void main(String[] args) {
        System.out.println(new LC300LongestIncreasingSubsequence().lengthOfLIS(new int[]{10,9,2,5,3,7,101,18}));
    }
}
